List of Topics
Экзамен по ДМ ещё не скоро, однако материал здесь будет постепенно пополняться.
Определения
- Бинарное отношение, Матрица бинарного отношения, Булево умножение матриц
- Мультимножество, Матрица бинарного мультиотношения
- Оператор замыкания
- Упорядоченное множество
- Отношение покрытия
- Изоморфизм упорядоченных множеств
- ПодЧУМ
- Операции над ЧУМами
- Линейное бинарное отношение
- Линейный порядок
- Линейно упорядоченное множество
- Нижняя и верхняя грани
- Инфимум и супремум
- Полурешётки и решётки
- Подрешетка
- Нуль, единица и дополнение решетки
- Равномощность множеств и кардинал, Неравенство кардинальных чисел
- Аксиомы ZFC
- Конечное множество, Бесконечное множество, Счетное множество
- Отношение полного порядка
- Число Каталана
- Перестановка множества
- Каноническая запись перестановки
- Число Стирлинга 1 рода
- Восходящий факториал
- Симметрическая группа, Действие перестановки
- Порядок
- Порождённая подмножеством группа
- Функция Ландау
- BWT
- Число Стирлинга второго рода и число Белла
- Рекуррентное соотношение
- Общее и частное решение
- ЛОРСПК
- О-символика
- Основные классы функций для асимптотики
- Базовые понятия о графах
- Базовые понятия о связности
- Подграфы
- Двудольный граф
- Эйлеров цикл, граф, маршрут
- Мост и точка сочленения
- 2-связный граф и блоки
- Гамильтонов цикл
- Изоморфизм графов
- Планарный граф
- Грань плоского графа
- Стягивание ребра
- Раскраска графа и хроматическое число
- Детерминированный конечный автомат
- Недетерминированный конечный автомат
- Основные определения и операции над языками
- Регулярный язык
- Булева функция
- ДНФ и СДНФ
Теоремы
- Теорема о матрице композиции
- Теорема о числе маршрутов в мультиорграфе
- Теорема о транзитивном замыкании
- Теорема о линейном порядке
- Эквивалентность минимальности, индуктивности и обрыва
- Теорема о решётке
- Теорема о равномощности подмножеству
- Теорема Бернштейна-Кантора
- Теорема Кантора о булеане
- Мощность континуума
- Теорема о счетном объединении
- Биномиальные коэффициенты и эквивалентность определений
- Свойства биномиальных коэффициентов
- Теорема о формуле чисел Каталана
- Теорема о стирании скобок
- Рекуррентная формула чисел Стирлинга
- Теорема о разложении восходящего факториала
- Теорема о группе и транспозициях
- Теорема Кэли
- Принцип включений-исключений
- Теорема о формуле чисел Стирлинга
- Теорема о рекуррентности чисел Стирлинга второго рода
- Теорема о числе сюрьекций
- Теорема о функции Эйлера
- Теорема о числе перемещений
- Лемма о подпространстве решений, Лемма о частных решениях, Лемма о независимости
- Теорема об общем решении
- Формула n-го простого числа
- Критерий двудольности
- Критерий полуэйлерова графа
- Критерий эйлерова графа
- Теорема о графе блоков
- Теорема Оре
- Теорема об укладке графа на сфере
- Теорема Эйлера о плоских графах
- Теорема Вагнера
- Теорема Хивуда
- Теорема Рабина-Скотта
- Теорема Клини
- Теорема о СДНФ
Утверждения
- Рефлексивное замыкание, Симметричное замыкание
- Эквивалентность изоморфности
- Сохранение свойств при изоморфизме
- Свойства join в ЧУМе
- Тождества поглощения
- Отношение порядка на решётке
- Дистрибутивность решётки
- Единственность дополнения
- Лемма о счетном подмножестве
- Формула разбиений на k слагаемых
- Формула Стирлинга
- Простейшие о-преобразования
- Лемма о рукопожатиях
- Лемма о существовании простой цепи
- Лемма о разрыве цикла
- Лемма о блоках
- Лемма о точке сочленения
- Лемма о циклах
- Лемма об удалении моста
- Лемма о жадной оценке
- Лемма о нижних оценках
- Лемма о раскраске блоков
- Лемма о степени вершины планарного графа
- Лемма о числе границ
- Следствие о числе ребер планарного графа
- Свойства операций над языками